package net.xuele.learn.dancing.tree;

import net.xuele.learn.dancing.TreeNode;

/**
 * @Author: yubo
 * @date: 13:51 2020/12/18
 * @Description: 类描述：leetcode 124
 * 该题的核心就是遍历树，找到各个子树的最大路径，这样便能找到总的最大路径了
 */

public class MaxPathSum {

    private int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        // 叶子节点
        if (root == null) return 0;
        // 左子树，如果子树路径和为负则应当置0，表示最大路径不包含该子树
        // 这样，在下面的判断中就不会再设计到该子树了
        int left = Math.max(0, maxPathSum(root.left));
        // 右子树，如果子树路径和为负则应当置0，表示最大路径不包含该子树
        int right = Math.max(0, maxPathSum(root.right));
        //  判断在该节点包含左右子树的路径和是否大于当前最大路径和
        max = Math.max(max, left + right + root.val);
        // 返回的是该子树的最大路径（取左右子树中最大的部分，left或者right都有可能是负数）
        return Math.max(left, right) + root.val;
    }
}
